package com.company.algo.DP.subseqProblem.editDistance;

import com.company.algo.debugUtils.DebugUtils;

/**
 * 115.不同的⼦序列
 * https://leetcode-cn.com/problems/distinct-subsequences/solution/dong-tai-gui-hua-yi-ci-ti-wei-li-jiang-j-enq0/
 * 给定⼀个字符串 s 和⼀个字符串 t ，计算在 s 的⼦序列中 t 出现的个数。
 * es: 输入：s = "rabbbit", t = "rabbit", 输出：3
 * 翻译：用字符串s对字符串t进行模式匹配，求解匹配成功的数量。
 * dp[i][j]：用s的前j个字符成功匹配t的前i个字符的个数。
 * dp[i][j] =
 * 考虑j为主要变量
 * 1.若t[i]!=s[j]，则只能沿用前面所成功匹配的个数即dp[i][j-1]
 * 2.若t[i]==s[j]，这时考虑两种情况，【选择】匹配或【不选择】
 * 例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不⽤s[3]来匹配，即⽤s[0：2]组成的bag。
 * 2.1. 若选择匹配，则成功匹配的数量为dp[i-1][j-1]
 * 2.2. 若不选择匹配，则成功匹配的数量为dp[i][j-1]
 * dp[i][0] = 0, dp[0][j] = 1, dp[0][0] = 1
 */
public class DiffSubSequence {
    public int numDistinct(String s, String t) {
        int m = t.length();
        int n = s.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int j = 0; j <= n; j++) dp[0][j] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (t.charAt(i - 1) != s.charAt(j - 1)) dp[i][j] = dp[i][j - 1];
                else dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
            }
            DebugUtils.printMatrix(dp);
            System.out.println("===============");
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        DiffSubSequence Main = new DiffSubSequence();
        System.out.println(Main.numDistinct("rabbbit", "rabbit"));
    }
}
